import java.util.ArrayList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=649 lang=java
 *
 * [649] Dota2 参议院
 */

// @lc code=start
class Solution {
    //标签是贪心，emmm，策略是每个人都会直接ban掉最近的后面一个人？
    //因为前面的已经行使过权利了，反而后面的没有行使过,所以最优策略是ban掉后面最近的一个让你
    // 如果后面没有另一个阵营的，那么ban掉前面的。
    // 直到最后找不到另一个阵营的即宣告胜利。
    public String predictPartyVictory(String senate) {
        //R和D 可以看作两个对象，这两个对象各自都有 自己被ban和ban别人的属性
        // 这个思路是借鉴的别人的，很棒的思路。
        int banR=0;
        int banD=0;
        char[] newSenate = senate.toCharArray();
        while(true) {
            /*
            好思路，就是不知道这个思路叫什么
            从字符串开始扫描，如果遇到R，那么banD++
            如果再遇到D，此时banD!=0的，所以会相应的被ban
            */
            for(int i=0;i<senate.length();i++) {
                if(newSenate[i]=='R') {
                    if(banR==0) {
                        banD++;
                    }else {
                        banR--;
                        newSenate[i]='X';
                    }
                }else if(newSenate[i]=='D') {
                    if(banD==0) {
                        banR++;
                    }else {
                        banD--;
                        newSenate[i]='X';
                    }
                }
            }
            boolean existD=false,existR=false;
            for(int i=0;i<newSenate.length;i++){
                if(newSenate[i]=='R'){
                    existR=true;
                }if(newSenate[i]=='D'){
                    existD=true;
                }
            }
            //如果两边都是true,说明还需要继续扫描一轮，那么继续下一轮，上一轮的状态还记着的
            if(existD == false){
                return "Radiant";
            }else if(existR == false){
                return "Dire";
            }
        }
    }
}
// @lc code=end

